# -*- coding: utf-8 -*-
"""
问题：二维平面上有n个点，如何快速计算出两个距离最近的点对？
"""
import math
import random


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def le_x(self, p):
        """比较两个点的x轴值大小，如果self.x小于p.x,返回True"""
        if self.x < p.x:
            return True
        return False

    def le_y(self, p):
        """比较两个点的y轴值大小，如果self.y小于p.y,返回True"""
        if self.y < p.y:
            return True
        return False

    def __repr__(self):
        return f"Point({self.x},{self.y})"


def cal_distance(p1, p2):
    """计算两点间的距离"""
    return math.sqrt(math.pow((p1.x - p2.x), 2) + math.pow((p1.y - p2.y), 2))


def get_closest(point_list):
    """二维平面上有n个点,计算最近的两个点"""
    if len(point_list) <= 1:
        return None

    point_list.sort(key=lambda p: p.x)
    print("new_point_list:", point_list)

    start_index = 0
    end_index = len(point_list) - 1

    ret = _get_closest(point_list, start_index, end_index)
    return ret


def _get_closest(point_list, start_index, end_index):
    if start_index >= end_index:
        return None

    if start_index + 1 == end_index:  # 两个点的情况
        return (
            (point_list[start_index], point_list[end_index]),
            cal_distance(point_list[start_index], point_list[end_index])
        )

    if start_index + 2 == end_index:  # 三个点的情况
        d1 = cal_distance(point_list[start_index], point_list[start_index + 1])
        d2 = cal_distance(point_list[start_index + 1], point_list[end_index])
        d3 = cal_distance(point_list[start_index], point_list[end_index])
        d_min = min([d1, d2, d3])
        if d_min == d1:
            return ((point_list[start_index], point_list[start_index + 1]), d1)
        elif d_min == d2:
            return ((point_list[start_index + 1], point_list[end_index]), d2)
        else:
            return ((point_list[start_index], point_list[end_index]), d3)

    # 多于三个点情况
    mid_index = start_index + (end_index - start_index) // 2
    ret_left = _get_closest(point_list, start_index, mid_index)
    ret_right = _get_closest(point_list, mid_index + 1, end_index)
    if ret_left is None and ret_right is not None:
        return ret_right
    elif ret_left is not None and ret_right is None:
        return ret_left

    min_left_right = min(ret_left[1], ret_right[1])
    tmp_min = min_left_right

    for i in range(start_index,mid_index+1,1):
        pass

    return


if __name__ == "__main__":
    point1 = Point(1, 2)
    point2 = Point(2, 3)
    ret = cal_distance(point1, point2)
    assert ret == math.sqrt(2)

    point_list = []
    for i in range(10):
        point_list.append(Point(random.randint(0, 100), random.randint(0, 100)))

    get_closest(point_list)
